A computer network is a geographically distributed collection of interconnected communication links and sub-networks (subnets) for transporting data between nodes, such as computers. Many types of computer networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). A LAN is an example of a subnet that provides relatively short distance communication among the interconnected nodes, whereas a WAN enables long distance communication over links provided by public or private telecommunications facilities. The nodes typically communicate by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate node, called a router, to extend the effective “size” of each network. Since management of a large system of interconnect computer networks can prove burdensome, smaller groups of computer networks may be maintained as routing domains or autonomous systems. The networks within an autonomous system are typically coupled together by conventional intradomain routers. These routers manage communication among local networks within their domains and communicate with each other using an intradomain routing (or an interior gateway) protocol. An example of such a protocol is the Enhanced Interior Gateway Routing Protocol (EIGRP) described in Cisco TCP/IP Routing Professional Reference, 2nd Addition, Chapter 4, pgs. 104-108 (1999) and Enhanced Interior Gateway Routing Protocol. 
The EIGRP protocol is a hybrid of distance vector and link state routing protocol technologies. A distance vector protocol computes a best path to a destination using distance (“cost” or hop count) and vector (the next hop) information. For EIGRP, the distance information is represented as a composite of available bandwidth, delay, load utilization and link reliability information that allows “fine tuning” of link characteristics to achieve optimal (or best) paths. Unlike most link state protocols that maintain information or “state” of the entire network topology, an EIGRP router only maintains state pertaining to reachable neighboring routers. As used herein, neighboring routers (or “neighbors”) are two routers that have interfaces to a common network, wherein an interface is a connection between a router and one of its attached networks. The state of each neighbor is stored in a neighbor data structure of the EIGRP router.
An adjacency is a relationship formed between selected neighbors for the purpose of exchanging routing information and abstracting the network topology. One or more router adjacencies may be established over an interface. Adjacencies are generally established, maintained and destroyed through the use of a conventional Hello protocol. Broadly stated, the Hello protocol ensures that communication between neighbors is bi-directional by periodically sending Hello packets out all router interfaces. Two routers become neighbors when they see each other's Hello packets over the common network.
The EIGRP protocol includes a Neighbor Discovery process that routers use to dynamically learn of other routers on their directly attached networks. Routers also use this process to discover when their neighbors become unreachable or inoperative. The Neighbor Discovery process is achieved with low overhead by periodically sending small Hello packets at a rate called the “HelloInterval”. The “HoldTime” is the amount of time, i.e., a multiple of the HelloInterval, that an EIGRP router will consider a neighbor alive without receiving a Hello packet. As long as the Hello packets are received from a neighbor within the HoldTime, the EIGRP router determines that the neighbor is alive and functioning; this, in turn, allows both neighbors to exchange (and update) routing information to thereby reach routing convergence. However, if the Hello packets are not received within the HoldTime, the router assumes that the neighbor no longer exists and “tears down” (destroys) the adjacency with the neighbor.
Often, it is desirable for a router to unilaterally decide to destroy an adjacency with its neighbor. In the case of a routing protocol that can maintain adjacencies over point-to-point interface connections, there may be electrical characteristics of the physical connection that disappear when the router “goes away” so that the neighbor can quickly detect that the router is gone. However, there are some point-to-point connection networks that do not provide electrical notification when a neighboring router disappears.
For a routing protocol that maintains adjacencies over multi-access interfaces, such as an Ethernet subnet interface, there are typically no electrical characteristics to inform the neighbors sharing that subnet that their neighboring router has disappeared. One way the router can inform the neighbors of its impending disappearance is to send an unreliable, “terminate” message over the multi-access interface indicating that the router is going away. Routing protocols that have unreliable (e.g., broadcast) capabilities can use this type of terminate mechanism to destroy adjacencies. Yet it is often undesirable to destroy all neighbor adjacencies using such an unreliable mechanism because there may be only a subset of adjacencies that needs terminating.
As noted, another conventional method of detecting neighbor (also referred to as “peer”) loss and, subsequently, destroying an adjacency is “time-based” through the absence of communication with the neighbor for a predetermined period of time. As with the case of the EIGRP protocol, it can be assumed that the neighbor no longer exists after expiration of that time period. However, it is also undesirable to assume the delay/latency associated with waiting the entire predetermined period of time, such as the HoldTime, to detect peer loss in order to destroy an existing adjacency. Rather, it is desirable to promptly notify neighbors of an intention to destroy adjacencies so that the adjacencies can be quickly removed, thereby “speeding-up” routing convergence and improving network stability.